package longestPalindrome;

public class LongestPalindrome {
    public  String longestPalindrome(String s) {
        int len = s.length();
        if (len <=1){
            return s;
        }
        int maxLen = 0;
        String longestPalindrome = "";
        for (int i = 0 ; i < len; i++) {
            int j = len - 1;
            if ((j-i+1)<=maxLen) {
                //若当前遍历的字串长度已经小于当前最大回文串 则没有继续寻找的意义了跳出循环
                break;
            }
            while (j >= i) {
                if (s.charAt(i) == s.charAt(j)) {
                    //若首尾相同则判断该子串是不是回文串
                    String su = s.substring(i, j + 1);
                    boolean isPalindrome = true;
                    for (int left = 0, right = su.length()-1;left <= right;left+=1, right-=1) {
                        if (su.charAt(left) != su.charAt(right)) {
                            isPalindrome = false;
                            break;
                        }
                    }
                    if (isPalindrome){
                        //是回文串 记录最大长度和最长回文串
                        if (maxLen < su.length()){
                            maxLen = su.length();
                            longestPalindrome = su;
                            break;
                        }
                    }
                }
                j -=1;
            }
        }

        return longestPalindrome;
    }


}
